A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.
For example,
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.
How many starting numbers below ten million will arrive at 89?
In [19]:
// this is awfully slow and inefficient - we should maybe keep an
// 89 or 1 cache for numbers (say) under 1000 so we don't have to
// keep recalc'ing them
let squareDigit n =
n * n
let squareDigits n =
string(n).ToCharArray()
|> Array.map (string >> int >> squareDigit)
|> Array.sum
let rec chain n =
if n = 89 || n = 1 then Some(n)
else chain (squareDigits n)
let arrives89 n =
match n with
| Some 89 -> true
| _ -> false
seq { 1 .. 10000000 }
|> Seq.map chain
|> Seq.filter arrives89
|> Seq.length
Out[19]:
In [ ]: